package cn.icatw.leetcode.editor.cn;
//给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
//
// 测试用例的答案是一个 32-位 整数。
//
//
//
// 示例 1:
//
//
//输入: nums = [2,3,-2,4]
//输出: 6
//解释: 子数组 [2,3] 有最大乘积 6。
//
//
// 示例 2:
//
//
//输入: nums = [-2,0,-1]
//输出: 0
//解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
//
//
//
// 提示:
//
//
// 1 <= nums.length <= 2 * 10⁴
// -10 <= nums[i] <= 10
// nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
//
//
// Related Topics 数组 动态规划 👍 2285 👎 0


//Java：乘积最大子数组
public class T152_MaximumProductSubarray {
    public static void main(String[] args) {
        Solution solution = new T152_MaximumProductSubarray().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    public class Solution {
        public int maxProduct(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }

            int n = nums.length;
            int maxProd = nums[0];
            int minProd = nums[0];
            int result = nums[0];

            // 从第 1 个元素开始遍历
            for (int i = 1; i < n; i++) {
                // 如果当前元素是负数，需要交换 maxProd 和 minProd
                if (nums[i] < 0) {
                    int temp = maxProd;
                    maxProd = minProd;
                    minProd = temp;
                }

                // 更新当前的最大值和最小值
                maxProd = Math.max(nums[i], maxProd * nums[i]);
                minProd = Math.min(nums[i], minProd * nums[i]);

                // 更新结果
                result = Math.max(result, maxProd);
            }

            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
